Dấu tích sớm nhất về việc loài người hiện diện tại Nouvelle-Calédonie có niên đại từ giai đoạn Lapita (khoảng 1600 TCN đến khoảng 500 TCN).[6] Người thuộc văn hoá Lapita là những người đi biển và làm nông có kỹ năng cao, có ảnh hưởng trên một khu vực lớn của Thái Bình Dương.[7]

Nhà thám hiểm người Anh James Cook là người châu Âu đầu tiên trông thấy Nouvelle-Calédonie, đó là vào ngày 4 tháng 9 năm 1774 trong hành trình thứ nhì của ông.[8] Ông đặt tên cho đảo là "New Caledonia", do phần đông bắc của đảo khiến ông nhớ đến Scotland.[8] Nhà thám hiểm người Pháp Jean-François de Galaup tiếp cận duyên hải phía tây của Grande Terre vào năm 1788, ngay trước khi ông mất tích, còn quần đảo Loyauté có người châu Âu lần đầu đến thăm vào năm 1796.[8] Từ sau đó cho đến năm 1840, chỉ ghi nhận được một vài tiếp xúc không thường xuyên với quần đảo.[8] Tiếp xúc trở nên thường xuyên hơn sau năm 1840, do mối quan tâm đến gỗ đàn hương từ Nouvelle-Calédonie.[6]

Do mậu dịch gỗ đàn hương suy thoái, thay thế nó là buôn bán những người bị nô lệ hoá từ Nouvelle-Calédonie, quần đảo Loyauté, New Hebrides, New Guinea, và quần đảo Solomon đi làm việc trong các đồn điền mía tại Fiji và Queensland.[9] Hoạt động mậu dịch này ngừng lại vào khởi đầu thế kỷ 20.[9] Nạn nhân của hoạt động này được gọi là "Kanaka".[9]

Các đoàn truyền giáo đầu tiên đến từ Hội Truyền giáo Luân Đôn và Dòng Các Thầy Maria, họ đến trong thập niên 1840.[10] Năm 1849, thuỷ thủ đoàn trên tàu Cutter của Hoa Kỳ bị thị tộc Pouma giết và ăn thịt.[11] Ăn thịt người là hành vi phổ biến trên khắp Nouvelle-Calédonie khi đó.[12]

Ngày 24 tháng 9 năm 1853, theo lệnh của Hoàng đế Napoléon III, Đô đốc Febvrier Despointes giành quyền chiếm hữu chính thức đối với Nouvelle-Calédonie và Port-de-France (Nouméa) được thành lập vào ngày 25 tháng 6 năm 1854.[8] Vài chục người định cư tự do đến duyên hải phía tây trong những năm sau đó.[8] Nouvelle-Calédonie trở thành một thuộc địa hình sự, và từ thập niên 1860 cho đến khi kết thúc vận chuyển tù nhân vào năm 1897, có khoản 22.000 tù nhân hình sự và chính trị bị đưa sang Nouvelle-Calédonie. Bulletin de la Société générale des prisons vào năm 1888 cho thấy rằng 10.428 tù nhân, bao gồm 2.329 người đã được phóng thích, ở trên đảo vào ngày 1 tháng 5 năm 1888, số lượng tù nhân lớn nhất và vượt xa số tù nhân bị giữ tại các trại tù hải ngoại khác.[13] Trong số các tù nhân, có nhiều chiến sĩ bị bắt giữ sau thất bại của Công xã Paris, trong đó có Henri Rochefort và Louise Michel.[14] Từ năm 1873 đến năm 1876, 4.200 tù nhân chính trị được chuyển đến Nouvelle-Calédonie.[8] Chỉ có 40 trong số này định cư tại thuộc địa, phần còn lại trở về Pháp sau khi được ân xá vào năm 1879 và 1880.[8]

Năm 1864, phát hiện được niken bên bờ sông Diahot và ngành khai mỏ bắt đầu một cách nghiêm túc khi Société Le Nickel được thành lập vào năm 1876.[15] Người Pháp nhập khẩu lao công đến làm việc tại các mỏ, ban đầu là từ các đảo lân cận, sau đó là từ Nhật Bản, Đông Ấn Hà Lan và Đông Dương thuộc Pháp.[14] Chính phủ Pháp cũng nỗ lực khuyến khích người châu Âu nhập cư, song không đạt nhiều thành công.[14]

Cư dân bản địa bị loại trừ khỏi kinh tế Pháp, thậm chí là trong việc làm công nhân khai mỏ, và họ cuối cùng bị hạn chế trong các khu vực riêng.[14] Điều này dây ra một phản ứng bạo lực vào năm 1878 khi tù trưởng cấp cao Atal của La Foa thống nhất nhiều bộ lạc tại miền trung và phát động chiến tranh du kích, khiến 200 người Pháp và 1.000 người Kanak thiệt mạng.[15] Người châu Âu mang đến các bệnh mới như đậu mùa và sởi, khiến nhiều người thiệt mạng.[11] Dân số người Kanak giảm từ 60.000 vào năm 1878 xuống còn 27.100 vào năm 1921, và quy mô công đồng không tăng trở lại cho đến thập niên 1930.[15]

Trong tháng 6 năm 1940, sau khi Pháp thất thủ trước quân Đức, Hội đồng toàn thể Nouvelle-Calédonie nhất trí ủng hộ chính phủ Pháp quốc Tự do, và đến tháng 9 vị thống đốc thân Vichy bị buộc phải rời đến Đông Dương.[15] Trong tháng 3 năm 1942, được Úc giúp đỡ,[16] lãnh thổ trở thành một căn cứ quan trọng của Đồng Minh,[15] và Nouméa là đại bản quan của lực lượng hải quân và lục quân của Hoa Kỳ tại Nam Thái Bình Dương.[17] Hạm đội từng đẩy lui lực lượng hải quân của Nhật Bản trong trận chiến biển Coral vào tháng 5 năm 1942 có căn cứ tại Nouméa.[15] Số lượng binh sĩ Hoa Kỳ đông đến 50.000, tương đương dân số lãnh thổ vào đương thời.[8]

Năm 1946, Nouvelle-Calédonie trở thành một lãnh thổ hải ngoại.[8] Đến năm 1953, toàn bộ cư dân Nouvelle-Calédonie thuộc mọi dân tộc đều được cấp quyền công dân Pháp.[18]

Dân số người gốc Âu và Polynesia dần tăng lên trong những năm dẫn đến bùng nổ niken 1969–1972, và người Melanesia trở thành thiểu số, song vẫn là dân tộc lớn nhất.[18] Từ năm 1976 đến năm 1988, Nouvelle-Calédonie thông qua năm đạo luật, đều gây nên bất mãn và hỗn loạn nghiêm trọng,[8] đỉnh điểm là vào năm 1988 khi xảy ra cuộc bắt cóc con tin đẫm máu tại Ouvéa. Các hiệp định Matignon được ký kết vào ngày 26 tháng 6 năm 1988 đảm bảo một thập niên ổn định. Hiệp nghị Nouméa được ký kết vào ngày 5 tháng 5 năm 1998, định ra cơ sở cho 20 năm chuyển đổi, theo đó dần chuyển giao thẩm quyền cho chính quyền địa phương.[8]